package huawei.checkandset;

public class J695 {
    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                int area = getArea(grid, i, j);
                max = Math.max(max, area);
            }
        }
        return max;
    }

    private int getArea(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length) {
            return 0;
        }
        if (j < 0 || j >= grid[i].length) {
            return 0;
        }
        if (grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
        return 1 + getArea(grid, i - 1, j) + getArea(grid, i + 1, j)
                + getArea(grid, i, j - 1) + getArea(grid, i, j + 1);
    }

    int[] parents;
    int[] ranks;

    public int maxAreaOfIsland2(int[][] grid) {
        parents = new int[]{grid.length * grid[0].length};
        ranks = new int[]{grid.length * grid[0].length};
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                int index = i * grid[i].length + j;
                if (grid[i][j] == 1) {
                    parents[index] = index;
                    ranks[index] = 1;
                } else {
                    parents[index] = -1;
                }
            }
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                int index = i * grid[i].length + j;
                if (grid[i][j] == 1) {
                    if (i - 1 >= 0 && grid[i - 1][j] == 1) {
                        merge(index, (i - 1) * grid[i].length + j);
                    }
                    if (i + 1 < grid.length && grid[i + 1][j] == 1) {
                        merge(index, (i + 1) * grid[i].length + j);
                    }
                    if (j - 1 >= 0 && grid[i][j - 1] == 1) {
                        merge(index, i * grid[i].length + j - 1);
                    }
                    if (j + 1 < grid[i].length && grid[i][j + 1] == 1) {
                        merge(index, i * grid[i].length + j + 1);
                    }
                }
            }
        }
        int max = 0;
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == i) {
                max = Math.max(max, ranks[i]);
            }
        }
        return max;
    }

    public int find(int index) {
        if (parents[index] == index) {
            return index;
        }
        return find(parents[index]);
    }

    /**
     * 合并和群组的总数量
     *
     * @param a
     * @param b
     * @return
     */
    public int merge(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) {
            return ranks[rootA];
        }
        if (ranks[rootA] > ranks[rootB]) {
            parents[rootB] = rootA;
            ranks[rootA] += ranks[rootB];
            return ranks[rootA];
        }
        parents[rootA] = rootB;
        ranks[rootB] += ranks[rootA];
        return ranks[rootB];
    }
}
